#include <iostream>
#include <utility>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;

void partition(vector<int>& nums,int l,int r,int& resl,int& resr,int x)
{
    int marksmall = l - 1;
    int markbig = r + 1;
    int i = l;
    while(i < markbig) {
        if(nums[i] < x)
        {
            swap(nums[marksmall+1],nums[i]);
            ++marksmall;
            ++i;
        }else if(nums[i] > x)
        {
            swap(nums[markbig-1],nums[i]);
            --markbig;
        }
        else {
            ++i;
        }
    }
    resl = marksmall+1;
    resr = markbig-1;
}


void quicksort(vector<int>& nums,int l,int r)
{
    if(r <= l) return;
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> distrib(l, r); // 定义分布范围[0, n]
    int random_num = distrib(gen);
    int x = nums[random_num];
    int resl = -1;
    int resr = -1;
    partition(nums,l,r,resl,resr,x);
    quicksort(nums,l,resl-1);
    quicksort(nums,resr+1,r);
}

vector<int> generateRandomArray(int max_size, int min_val, int max_val) {
  int size = rand() % max_size + 1; // 保证至少1个元素
  vector<int> arr(size);
  for (int i = 0; i < size; ++i) {
    arr[i] = rand() % (max_val - min_val + 1) + min_val;
  }
  return arr;
}

int main() {
  srand(time(0)); // 设置随机种子
  const int TEST_TIMES = 1000;
  const int MAX_SIZE = 1000;
  const int MIN_VAL = -1000;
  const int MAX_VAL = 1000;
  for (int i = 0; i < TEST_TIMES; ++i) {
    vector<int> arr = generateRandomArray(MAX_SIZE, MIN_VAL, MAX_VAL);
    vector<int> a = arr;
    std::sort(arr.begin(), arr.end());
    quicksort(a,0,a.size()-1);
    for(int i = 0; i < arr.size();++i)
    {
        if(a[i] != arr[i])
        {
            cout<<"Error: ";
            for(int i =0; i < a.size();++i)
            {
                cout<<a[i]<<" ";
            }
            cout<<endl;
            for(int i =0; i < arr.size();++i)
            {
                cout<<arr[i]<<" ";
            }
            cout<<endl;
            return 1;
        }
    }
  }
  cout << "所有 " << TEST_TIMES << " 次测试通过！" << endl;
  return 0;
}
